package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/5 15:19
 *
 剪绳子:
 1,动态规划:
 dpi为长度为i的绳子分段乘积最大值
 */

public class Main14 {

    public int cutRope(int target) {
        //特判
        if(target<=3){
            return target-1;
        }
        int dp[]=new int[target+1];
        dp[1]=1;
        dp[2]=2;//如果不初始化为2，那么dp[4]=2*dp[2]=1
        dp[3]=3;//同理，不然dp[3]=2了，不如不切时候
        for(int i=4;i<=target;++i){
            for(int j=1;j<i;++j){
                dp[i]=Math.max(dp[i],j*dp[i-j]);
            }
        }
        return dp[target];
    }
}
